{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "37cd26f7-b946-4ab3-9f82-3fed934045fd",
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "\n",
    "# Set the environment variable to avoid memory leak warning\n",
    "os.environ[\"OMP_NUM_THREADS\"] = \"2\"\n",
    "\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "\n",
    "from sklearn.cluster import KMeans\n",
    "from sklearn.cluster import DBSCAN\n",
    "from sklearn.datasets import make_moons\n",
    "from sklearn.datasets import make_blobs\n",
    "\n",
    "import time\n",
    "\n",
    "import cv2\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "color_list = ['tab:blue', 'tab:orange', 'tab:green', 'tab:red', 'tab:purple', 'tab:brown', 'tab:pink', 'tab:gray', 'tab:olive', 'tab:cyan']\n",
    "\n",
    "label_size = 18 # Label size\n",
    "ticklabel_size = 14 # Tick label size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "e109b145-1389-4a7a-9828-bb31e2d3d313",
   "metadata": {},
   "outputs": [],
   "source": [
    "#1.实现k-Means聚类算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9c7acbb0-edad-4577-8399-f5a1e1a38123",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Generate 1-D data\n",
    "np.random.seed(42)\n",
    "x = np.random.rand(100)\n",
    "\n",
    "# Plot\n",
    "fig, ax = plt.subplots(figsize=(7,7))\n",
    "ax.scatter(x, x, edgecolor='black', facecolor='white', linewidth=2, s=7**2)\n",
    "ax.tick_params(axis='both', which='major', labelsize=ticklabel_size) # Set tick label size\n",
    "\n",
    "# plt.savefig('1D_data_base.png', dpi=300) # Make figure clearer\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f450eb8d-1a2a-4bd0-8c99-2acb341d6db4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# k-Means clustering\n",
    "k = 2\n",
    "\n",
    "# Initialize cluster centers\n",
    "cluster_centers = [0.1, 0.2]\n",
    "\n",
    "# Initialize distance array\n",
    "distance = np.zeros((len(x), k))\n",
    "\n",
    "# Intercation\n",
    "max_iter = 10\n",
    "for iter_id in range(max_iter):\n",
    "    # Calculate distance between points to each center\n",
    "    for i in range(k):\n",
    "        distance[:,i] = np.abs(x - cluster_centers[i])\n",
    "\n",
    "    # Assign to closest centroid\n",
    "    cluster_idx = np.argmin(distance, axis=1)\n",
    "\n",
    "    # Display process\n",
    "    fig, ax = plt.subplots(figsize=(7,7))\n",
    "\n",
    "    # Display points close to center 1\n",
    "    ax.scatter(x[cluster_idx == 0], x[cluster_idx == 0], edgecolor=color_list[0], facecolor='white', linewidth=2, s=7**2)\n",
    "    ax.axvline(x=cluster_centers[0], color=color_list[0], linestyle='--', linewidth=2)\n",
    "\n",
    "    # Display points close to center 2\n",
    "    ax.scatter(x[cluster_idx == 1], x[cluster_idx == 1], edgecolor=color_list[1], facecolor='white', linewidth=2, s=7**2)\n",
    "    ax.axvline(x=cluster_centers[1], color=color_list[1], linestyle='--', linewidth=2)\n",
    "\n",
    "    ax.tick_params(axis='both', which='major', labelsize=ticklabel_size) # Set tick label size\n",
    "    ax.set_title(f'Interation: {iter_id}, C1: {cluster_centers[0]:.2f}, C2: {cluster_centers[1]:.2f}', fontsize=label_size)\n",
    "\n",
    "    # plt.savefig(f'1D_data_iter{iter_id}.png', dpi=300) # Make figure clearer\n",
    "    plt.show()\n",
    "\n",
    "    # Update cluster centers\n",
    "    for i in range(k):\n",
    "        cluster_centers[i] = np.mean(x[cluster_idx == i])\n",
    "\n",
    "# Display process\n",
    "fig, ax = plt.subplots(figsize=(7,7))\n",
    "\n",
    "# Display points close to center 1\n",
    "ax.scatter(x[cluster_idx == 0], x[cluster_idx == 0], edgecolor=color_list[0], facecolor='white', linewidth=2, s=7**2)\n",
    "ax.axvline(x=cluster_centers[0], color=color_list[0], linestyle='--', linewidth=2)\n",
    "\n",
    "# Display points close to center 2\n",
    "ax.scatter(x[cluster_idx == 1], x[cluster_idx == 1], edgecolor=color_list[1], facecolor='white', linewidth=2, s=7**2)\n",
    "ax.axvline(x=cluster_centers[1], color=color_list[1], linestyle='--', linewidth=2)\n",
    "\n",
    "ax.tick_params(axis='both', which='major', labelsize=ticklabel_size) # Set tick label size\n",
    "ax.set_title(f'Interation: {iter_id}, C1: {cluster_centers[0]:.2f}, C2: {cluster_centers[1]:.2f}', fontsize=label_size)\n",
    "\n",
    "#plt.savefig(f'1D_data_iter{iter_id}.png', dpi=300) # Make figure clearer\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "2fe032a8-3ab6-471a-93a2-002e1feccfb5",
   "metadata": {},
   "outputs": [],
   "source": [
    "#2.使用肘部法确定最佳k值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6699415b-006b-445a-834b-37b261541b1c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Using make_blobs to generate data of ten clustering\n",
    "X_mb, y_mb = make_blobs(n_samples=500, n_features=2, centers=6, random_state=42)\n",
    "\n",
    "fig, ax = plt.subplots(figsize=(10,10))\n",
    "ax.scatter(X_mb[:, 0], X_mb[:, 1], marker=\"o\", c=y_mb, s=10**2, edgecolor=\"k\")\n",
    "plt.axis('off')\n",
    "# plt.savefig(f'make_blobs_base.png', dpi=300)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5e3491b1-0715-4aee-a946-4ddcea3a208d",
   "metadata": {},
   "outputs": [],
   "source": [
    "k_list = np.arange(2, 20, 1)\n",
    "sse_list = np.zeros(len(k_list))\n",
    "\n",
    "mdl_km_list = []\n",
    "for i in range(len(k_list)):\n",
    "    mdl_km = KMeans(n_clusters=k_list[i], n_init='auto')\n",
    "    mdl_km.fit(X_mb)\n",
    "    mdl_km_list.append(mdl_km)\n",
    "    sse_list[i] = mdl_km.inertia_\n",
    "\n",
    "# Plot sse_list\n",
    "fig, ax = plt.subplots(figsize=(8,6))\n",
    "ax.plot(k_list, sse_list, marker='o', linestyle='-', color='tab:blue')\n",
    "ax.set_xticks(k_list)\n",
    "ax.set_xlabel('Number of clusters (k)', fontsize=label_size)\n",
    "ax.set_ylabel('SSE', fontsize=label_size)\n",
    "ax.tick_params(axis='both', which='major', labelsize=ticklabel_size) # Set tick label size\n",
    "# plt.savefig(f'make_blobs_sse.png', dpi=300)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ca3f68aa-a03c-4e7d-aa38-a37f956092d7",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Display clustering result of k = 5, 6, 7\n",
    "k_disp = [5, 6, 7]\n",
    "for k in k_disp:\n",
    "    mdl_km = mdl_km_list[k-2]\n",
    "\n",
    "    fig, ax = plt.subplots(figsize=(10,10))\n",
    "    ax.scatter(X_mb[:, 0], X_mb[:, 1], marker=\"o\", c=mdl_km_list[k-2].labels_, s=10**2, edgecolor=\"k\")\n",
    "    ax.set_title(f'Number of clusters (k): {k}', fontsize=label_size)\n",
    "    plt.axis('off')\n",
    "\n",
    "    # plt.savefig(f'make_blobs_{k}.png', dpi=300)\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "606f8d83-945d-4f7e-8830-31566cc5c1e0",
   "metadata": {},
   "outputs": [],
   "source": [
    "#3.使用OpenCV库读取图像数据，并转换为灰度图像"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ecf9693c-a925-4946-8bb3-b6df4ccb13f7",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load the car number image\n",
    "image_carno = cv2.imread('D:/car_num.jpg')\n",
    "\n",
    "# Convert from BGR to RGB\n",
    "image_carno = cv2.cvtColor(image_carno, cv2.COLOR_BGR2RGB)\n",
    "\n",
    "# Display the image\n",
    "fig, ax = plt.subplots(figsize=(7,7))\n",
    "img = ax.imshow(image_carno)\n",
    "plt.axis('off')  # Hide axes\n",
    "# plt.savefig('carno_base.png', dpi=300) # Make figure clearer\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d71333e4-26be-40d4-82f7-2c69b98de5e7",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Change image_carno into grey image\n",
    "image_carno_grey = cv2.cvtColor(image_carno, cv2.COLOR_BGR2GRAY)\n",
    "\n",
    "# Display the image\n",
    "fig, ax = plt.subplots(figsize=(7,7))\n",
    "img = ax.imshow(image_carno_grey, cmap='gray')\n",
    "plt.axis('off')  # Hide axes\n",
    "# plt.savefig('carno_grey.png', dpi=300) # Make figure clearer\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "7d56464e-a772-45cf-92ea-a3c04d612a34",
   "metadata": {},
   "outputs": [],
   "source": [
    "#4.使用k-Means生成蒙版，区分灰度图像的前景与背景"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7451572a-e259-4a7d-9115-c80892d37c5a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Reshape image_carno_grey into a 1-D vector\n",
    "x = image_carno_grey.reshape(-1)\n",
    "\n",
    "# Using k-Means to separate background and foreground by pixels\n",
    "k = 2\n",
    "\n",
    "# Initialize cluster centers\n",
    "cluster_centers = np.random.rand(k) * 255\n",
    "start_centers = cluster_centers.copy()\n",
    "\n",
    "# Initialize distance array\n",
    "distance = np.zeros((len(x), k))\n",
    "\n",
    "# Intercation\n",
    "start_time = time.time()\n",
    "max_iter = 1000\n",
    "for iter_id in range(max_iter):\n",
    "    # Calculate distance between points to each center\n",
    "    for i in range(k):\n",
    "        distance[:,i] = np.abs(x - cluster_centers[i])\n",
    "\n",
    "    # Assign to closest centroid\n",
    "    cluster_idx = np.argmin(distance, axis=1)\n",
    "\n",
    "    # Update cluster centers\n",
    "    cluster_centers_prior = cluster_centers.copy()\n",
    "    for i in range(k):\n",
    "        cluster_centers[i] = np.mean(x[cluster_idx == i])\n",
    "\n",
    "    # Check if cluster_centers are stable enough to stop training\n",
    "    print(f'Iteration {iter_id}: Updated centers {cluster_centers}, Prior centers {cluster_centers_prior}')\n",
    "    if np.sum(np.abs(cluster_centers-cluster_centers_prior)) == 0:\n",
    "        break\n",
    "\n",
    "    cluster_centers_prior = cluster_centers\n",
    "\n",
    "end_time = time.time()\n",
    "print(f'Stop after iteration {iter_id}, time consumption is {end_time-start_time}')\n",
    "\n",
    "# Generate segmentation mask\n",
    "carno_mask_pixel = np.zeros_like(cluster_idx)\n",
    "low_value_cluster = np.argmin(cluster_centers)\n",
    "carno_mask_pixel[cluster_idx != low_value_cluster] = 1 # Set pixels with higher grey value to 1\n",
    "carno_mask_pixel = carno_mask_pixel.reshape(image_carno_grey.shape)\n",
    "\n",
    "# Display the mask\n",
    "fig, ax = plt.subplots(figsize=(7,7))\n",
    "img = ax.imshow(carno_mask_pixel, cmap='gray')\n",
    "ax.set_title(f'Final Centers: {cluster_centers}, Iteration: {iter_id}', fontsize=label_size)\n",
    "plt.axis('off')  # Hide axes\n",
    "# plt.savefig('carno_mask_pixel_2.png', dpi=300) # Make figure clearer\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "ead05940-fbfa-4294-8fdf-d29a4140f6ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "#5.\t使用k-Means对像素颜色进行聚类，观察不同k值条件下的结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "62aba2d7-d5a4-47b0-a4ab-2b2ab03c7e03",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load the car number image\n",
    "image_bmwk = cv2.imread('D:/bmwk.png')\n",
    "\n",
    "# Convert from BGR to RGB\n",
    "image_bmwk_rgb = cv2.cvtColor(image_bmwk, cv2.COLOR_BGR2RGB)\n",
    "\n",
    "x_r = image_bmwk_rgb[:, :, 0].reshape(-1) # Store colors in red channel\n",
    "x_g = image_bmwk_rgb[:, :, 1].reshape(-1) # Store colors in green channel\n",
    "x_b = image_bmwk_rgb[:, :, 2].reshape(-1) # Store colors in blue channel\n",
    "\n",
    "# Display the image with no margin\n",
    "plt.figure(figsize=(image_bmwk_rgb.shape[1]/100, image_bmwk_rgb.shape[0]/100))  # Convert pixels to inches\n",
    "plt.imshow(image_bmwk_rgb)\n",
    "plt.axis('off')  # Hide axes\n",
    "plt.subplots_adjust(left=0, right=1, top=1, bottom=0)  # Remove margins\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0bc547f5-81d5-4696-b52b-0af652345ea4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def KMeansImage(img, k):\n",
    "    # Get image size\n",
    "    w, h, c = img.shape\n",
    "\n",
    "    # Reshape image along channel\n",
    "    x = np.reshape(img, (w * h, c))\n",
    "\n",
    "    # Train k-Means model\n",
    "    mdl_km = KMeans(n_clusters=k, n_init='auto')\n",
    "    mdl_km.fit(x)\n",
    "\n",
    "    # Predict labels of each pixels\n",
    "    labels = mdl_km.predict(x).reshape(w, h)\n",
    "\n",
    "    # Get centers\n",
    "    center_colors = mdl_km.cluster_centers_ / 255.0\n",
    "\n",
    "    # Use center colors to generate compressed image\n",
    "    img_comp = np.zeros((w, h, c))\n",
    "    for i in range(w):\n",
    "        for j in range(h):\n",
    "            img_comp[i][j] = center_colors[labels[i][j]]\n",
    "    return img_comp, center_colors\n",
    "\n",
    "claster_num = [2, 4, 8, 16, 32, 64]\n",
    "for k in claster_num:\n",
    "    img_comp, center_colors = KMeansImage(image_bmwk_rgb, k)\n",
    "\n",
    "    # Display center colors\n",
    "    fig, ax = plt.subplots(figsize=(16,1))\n",
    "    ax.imshow([center_colors])\n",
    "    plt.axis('off')\n",
    "    # plt.savefig(f'bmwk_center_{k}.png', dpi=300)\n",
    "    plt.show()\n",
    "\n",
    "     # Display compressed image\n",
    "    plt.figure(figsize=(image_bmwk_rgb.shape[1]/100, image_bmwk_rgb.shape[0]/100))  # Convert pixels to inches\n",
    "    plt.imshow(img_comp)\n",
    "    plt.axis('off')\n",
    "    plt.subplots_adjust(left=0, right=1, top=1, bottom=0)  # Remove margins\n",
    "    # plt.savefig(f'bmwk_comp_{k}.png', format='png', bbox_inches='tight', pad_inches=0)\n",
    "    plt.show()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
